﻿// 0807train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>

using namespace std;

/*
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 */

int solve01(vector<int>& nums)
{
    int vec_size = nums.size();
    vector<int>dynamic_grid(vec_size,1);

    for (int curr=1; curr<vec_size;curr++)
    {
        for (int prev=0; prev<curr; prev++)
        {
            if (nums[prev]<nums[curr])
            {
                dynamic_grid[curr] = max(dynamic_grid[curr], dynamic_grid[prev] + 1);
            }

        }
    }

    int result = 1;

    for (auto&length:dynamic_grid)
    {
        result = max(result, length);
    }

    return result;
    //solve01------
}


/*
 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
 注意 这个数列必须是 严格 递增的。

 示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
 */

int solve02(vector<int>& nums)
{
    vector<int>origin_vec = nums;
    int vec_size = origin_vec.size();

    vector<int>dynamic_grid(vec_size, 1);

    int max_length = 1;
    vector<int>count_vec(vec_size, 1);
    for (int curr=0; curr<vec_size; curr++)
    {
        for (int prev=0; prev< curr; prev++)
        {
            if (origin_vec[prev] >= origin_vec[curr])
                continue;

            //前提，origin_vec[prev]<origin_vec[curr]
            //最长子序列新增一个
            if (dynamic_grid[curr]<dynamic_grid[prev]+1)
            {
                dynamic_grid[curr] = dynamic_grid[prev] + 1;
                count_vec[curr] = count_vec[prev];
            }
            else if(dynamic_grid[curr] == dynamic_grid[prev]+1)
			{
                count_vec[curr] += count_vec[prev];
			}
            max_length = max(max_length, dynamic_grid[curr]);
        }
    }

    //for (auto&num:dynamic_grid)
    //{
    //    cout << num << ' ';
    //}
    //cout << '\n';

    if (max_length==1)
    {
        return vec_size;
    }

    
    int result = 0;
    for (int i = 0; i < vec_size; ++i) {
        if (dynamic_grid[i] == max_length) {
            result += count_vec[i];
        }
    }

    return result;
    //solve02
}


/*
 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；
否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5]
输出：true
解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1]
输出：false
解释：不存在满足题意的三元组
 */

bool solve03(vector<int>&nums)
{
    vector<int>origin_vec = nums;
    int vec_size = origin_vec.size();

    vector<int>dynamic_vec(vec_size, 1);

    bool result = false;
    for (int curr=1; curr<vec_size; curr++)
    {
        for (int prev=0; prev< curr; prev++)
        {
            if (origin_vec[curr]>origin_vec[prev])
            {
                dynamic_vec[curr] = max(dynamic_vec[curr], dynamic_vec[prev]+1);
            }

            if (dynamic_vec[curr]==3)
            {
                result = true;
                break;
            }

        }

    }

    return result;
    //solve03------
}


bool solve031(vector<int>& nums)
{
    int first = INT_MAX;
    int second = INT_MAX;

    for (auto&third:nums)
    {
        if (third <= first)
        {
            first = third;
        }
        else if (third>second)
        {
            return true;
        }
        else
        {
            second = third;
        }

        //for---
    }
    return false;
    //solve031------
}


/*
 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

 输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
 */

int solve04(vector<int>& nums1, vector<int>& nums2) {

    //记录nums1前i个数，nums2前j个数中的最长子数组
    vector<int>col_vec = nums1;
    vector<int>row_vec = nums2;

    int col_size = nums1.size()+1;
    int row_size = nums2.size()+1;

    vector<vector<int>>dynamic_vec(row_size, vector<int>(col_size, 0));

    int max_length = 0;
    //第1行，nums2为空，全是0
    //第1列，nums1为空，全是0
    //row=1,col=1开始计算
    for (int row=1; row<row_size; row++)
    {
        for (int col=1; col<col_size; col++)
        {
            if (col_vec[col-1]==row_vec[row-1])
            {
                //重复子数组，
                dynamic_vec[row][col] = dynamic_vec[row - 1][col - 1] + 1;
            }
            max_length = max(max_length, dynamic_vec[row][col]);
        }
    }

    //for (auto&mini_vec:dynamic_vec)
    //{
    //    for (auto&num:mini_vec)
    //    {
    //        cout << num << ' ';
    //    }
    //    cout << '\n';
    //}

    return max_length;
    //solve04---
}


/*
 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如
 果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：
它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。


示例 1：
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。
 */

int solve05(string&text1, string&text2)
{
    string col_str = text1;
    string row_str = text2;

    int col_size = text1.size()+1;
    int row_size = text2.size()+1;

    vector<vector<int>>dynamic_grid(row_size, vector<int>(col_size));

	//第0行，row_str是空串，全为0
    //第0列，col_str是空串，全为0
    //所以从1行1列开始计，
    for (int row=1; row<row_size; row++)
    {
        for (int col=1; col<col_size; col++)
        {
            //换成索引，记得-1
            if (col_str[col-1]==row_str[row-1])
            {
	            //相等，表明char一定在子序列中
                dynamic_grid[row][col] = dynamic_grid[row - 1][col - 1] + 1;
            }
            else
            {
                //不相等一共3种情况
                //1col_char在子序列中，2row_char在子序列中，3两个都不在子序列中
                //三种情况取最大的
                int max_length = max(dynamic_grid[row][col-1], dynamic_grid[row-1][col]);
                max_length = max(max_length, dynamic_grid[row-1][col-1]);
                dynamic_grid[row][col] = max_length;
            }
        }
    }

    return dynamic_grid[row_size - 1][col_size - 1];
    //solve05
}

int main()
{
	{
        //text1 = "abcde", text2 = "ace"
        string text1 = "abcde", text2 = "ace";
        cout << solve05(text1, text2);
        return 0;
	}


	{
		//A: [1, 2, 3, 2, 1] B : [3, 2, 1, 4, 7]
        vector<int>vec_1 = { 1, 2, 3, 2, 1 };
        vector<int>vec_2 = { 3, 2, 1, 4, 7 };
        cout << solve04(vec_1, vec_2);
		return 0;
	}


	{
        vector<int>nums = { 1, 2, 3, 4, 5 };
        cout << solve03(nums);
        return 0;
	}

	{
		//[1, 3, 5, 4, 7] 2
        //[1,2,4,3,5,4,7,2] 3
        vector<int>nums = { 1,2,4,3,5,4,7,2 };
        cout << solve02(nums);

        return 0;
	}

    //[0,3,1,6,2,2,7] 4
    //[1,3,6,7,9,4,10,5,6] 6
    vector<int>nums = { 1,3,6,7,9,4,10,5,6 };
    cout << solve01(nums);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
